Search Results

Documents authored by Gaitonde, Jason

Document
DOI: 10.4230/LIPIcs.ITCS.2023.52
Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence

Authors: Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Online advertising via auctions increasingly dominates the marketing landscape. A typical advertiser may participate in thousands of auctions each day with bids tailored to a variety of signals about user demographics and intent. These auctions are strategically linked through a global budget constraint. To help address the difficulty of bidding, many major online platforms now provide automated budget management via a flexible approach called budget pacing: rather than bidding directly, an advertiser specifies a global budget target and a maximum willingness-to-pay for different types of advertising opportunities. The specified maximums are then scaled down (or "paced") by a multiplier so that the realized total spend matches the target budget. These automated bidders are now near-universally adopted across all mature advertising platforms, raising pressing questions about market outcomes that arise when advertisers use budget pacing simultaneously. In this paper we study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in repeated auctions with budgets. We show that when agents simultaneously use a natural form of gradient-based pacing, the liquid welfare obtained over the course of the dynamics is at least half the optimal liquid welfare obtainable by any allocation rule, matching the best possible bound for static auctions even in pure Nash equilibria [Aggarwal et al., WINE 2019; Babaioff et al., ITCS 2021]. In contrast to prior work, these results hold without requiring convergence of the dynamics, circumventing known computational obstacles of finding equilibria [Chen et al., EC 2021]. Our result is robust to the correlation structure among agents' valuations and holds for any core auction, a broad class that includes first-price, second-price, and GSP auctions. We complement the aggregate guarantees by showing that an agent using such pacing algorithms achieves an O(T^{3/4}) regret relative to the value obtained by the best fixed pacing multiplier in hindsight in stochastic bidding environments. Compared to past work, this result applies to more general auctions and extends to adversarial settings with respect to dynamic regret.
Cite as

Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 52:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gaitonde_et_al:LIPIcs.ITCS.2023.52,
  author =	{Gaitonde, Jason and Li, Yingkai and Light, Bar and Lucier, Brendan and Slivkins, Aleksandrs},
  title =	{{Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{52:1--52:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.52},
  URN =		{urn:nbn:de:0030-drops-175557},
  doi =		{10.4230/LIPIcs.ITCS.2023.52},
  annote =	{Keywords: repeated auctions with budgets, pacing, learning in auctions}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.16
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Authors: Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
Fast mixing of random walks on hypergraphs (simplicial complexes) has recently led to myriad breakthroughs throughout theoretical computer science. Many important applications, however, (e.g. to LTCs, 2-2 games) rely on a more general class of underlying structures called posets, and crucially take advantage of non-simplicial structure. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how regularity controls the spectral decay and edge-expansion of corresponding random walks. We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit strong (even exponential) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly - a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on expanding posets in the 𝓁₂-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on 𝓁_∞ rather than 𝓁₂-structure.
Cite as

Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gaitonde_et_al:LIPIcs.APPROX/RANDOM.2022.16,
  author =	{Gaitonde, Jason and Hopkins, Max and Kaufman, Tali and Lovett, Shachar and Zhang, Ruizhe},
  title =	{{Eigenstripping, Spectral Decay, and Edge-Expansion on Posets}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.16},
  URN =		{urn:nbn:de:0030-drops-171381},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.16},
  annote =	{Keywords: High-dimensional expanders, posets, eposets}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.10
Fractional Pseudorandom Generators from Any Fourier Level

Authors: Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the k-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with k. This interpolates previous works, which either require Fourier bounds on all levels [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. As an example, we show that for polynomial error, Fourier bounds on the first O(log n) levels is sufficient to recover the seed length in [Chattopadhyay et al., 2019], which requires bounds on the entire tail. We obtain our results by an alternate analysis of fractional PRGs using Taylor’s theorem and bounding the degree-k Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the L₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for 𝔽₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009].
Cite as

Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. Fractional Pseudorandom Generators from Any Fourier Level. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2021.10,
  author =	{Chattopadhyay, Eshan and Gaitonde, Jason and Lee, Chin Ho and Lovett, Shachar and Shetty, Abhishek},
  title =	{{Fractional Pseudorandom Generators from Any Fourier Level}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.10},
  URN =		{urn:nbn:de:0030-drops-142843},
  doi =		{10.4230/LIPIcs.CCC.2021.10},
  annote =	{Keywords: Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact